#include<iostream>
#include<stdint.h>
#include<string.h>
#include <vector>

int find(int* array, int start, int end, int val)
{
    if (NULL == array || start > end) return 0;

    int mid = (start + end) / 2;
    mid = (end - start) * (val - array[start]) / (array[end] - array[start]) + start;
    if (array[mid] == val) return mid;
    else if (array[mid] > val) return find(array, start, mid - 1, val);
    else return find(array, mid + 1, end, val);
}

template <int N>
//void selectSort
void bubleSort(int (&a)[N])
{
    std::cout << N << std::endl;
    for (int i = N; i > 0; --i) {
        int idx = i;
        for (int j = 0; j < i; ++j) {
            if (a[idx] < a[j]) idx = j;
        }
        if (idx != i) std::swap(a[i], a[idx]);
    }
}

template <int N>
void insertSort(int (&a)[N])
{
    for (int i = 1; i < N; ++i) {
        int tmp = a[i];
        for (int j = i - 1; j >= 0 && a[j] > tmp; --j) {
            a[j+1] = a[j];
        }
        a[j+1] = tmp;

    }
}

int main(int argc, char** argv)
{
    int a[] = {3,5,6,7,8,9, 1, 2, 4};
    std::cout << find(a, 0, 8, 4) << std::endl;
    bubleSort(a);
    for (int i = 0; i < 9; ++i) {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}


